{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Optimal Division"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #math #dynamic-programming"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #数学 #动态规划"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: optimalDivision"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #最优除法"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定一正整数数组<strong> </strong><code>nums</code><strong>，</strong><code>nums</code> 中的相邻整数将进行浮点除法。例如，&nbsp;[2,3,4] -&gt; 2 / 3 / 4 。</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>例如，<code>nums = [2,3,4]</code>，我们将求表达式的值&nbsp;<code>\"2/3/4\"</code>。</li>\n",
    "</ul>\n",
    "\n",
    "<p>但是，你可以在任意位置添加任意数目的括号，来改变算数的优先级。你需要找出怎么添加括号，以便计算后的表达式的值为最大值。</p>\n",
    "\n",
    "<p>以字符串格式返回具有最大值的对应表达式。</p>\n",
    "\n",
    "<p><strong>注意：</strong>你的表达式不应该包含多余的括号。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> [1000,100,10,2]\n",
    "<strong>输出:</strong> \"1000/(100/10/2)\"\n",
    "<strong>解释: </strong>1000/(100/10/2) = 1000/((100/10)/2) = 200\n",
    "但是，以下加粗的括号 \"1000/(<strong>(</strong>100/10<strong>)</strong>/2)\" 是冗余的，\n",
    "因为他们并不影响操作的优先级，所以你需要返回 \"1000/(100/10/2)\"。\n",
    "\n",
    "其他用例:\n",
    "1000/(100/10)/2 = 50\n",
    "1000/(100/(10/2)) = 50\n",
    "1000/100/10/2 = 0.5\n",
    "1000/100/(10/2) = 2\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 2:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> nums = [2,3,4]\n",
    "<strong>输出:</strong> \"2/(3/4)\"\n",
    "<strong>解释:</strong> (2/(3/4)) = 8/3 = 2.667\n",
    "可以看出，在尝试了所有的可能性之后，我们无法得到一个结果大于 2.667 的表达式。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>说明:</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= nums.length &lt;= 10</code></li>\n",
    "\t<li><code>2 &lt;= nums[i] &lt;= 1000</code></li>\n",
    "\t<li>对于给定的输入只有一种最优除法。</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [optimal-division](https://leetcode.cn/problems/optimal-division/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [optimal-division](https://leetcode.cn/problems/optimal-division/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[1000,100,10,2]', '[2,3,4]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def optimalDivision(self, nums: List[int]) -> str:\n",
    "        n = len(nums)\n",
    "        if n == 1:\n",
    "            return str(nums[0])\n",
    "        elif n == 2:\n",
    "            return \"{}/{}\".format(nums[0],nums[1])\n",
    "        else:\n",
    "            return \"{}/({})\".format(nums[0],'/'.join(str(num) for num in nums[1:]))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def optimalDivision(self, nums: List[int]) -> str:\n",
    "\n",
    "        nums=list(map(str,nums))\n",
    "\n",
    "        if len(nums)>2:\n",
    "\n",
    "            nums[1]='('+nums[1]\n",
    "\n",
    "            nums[-1]=nums[-1]+')'\n",
    "\n",
    "        return \"/\".join(nums)\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def optimalDivision(self, nums: List[int]) -> str:\n",
    "        if len(nums) == 1:\n",
    "            return str(nums[0])\n",
    "        if len(nums) == 2:\n",
    "            return str(nums[0]) + \"/\" + str(nums[1])\n",
    "        return str(nums[0]) + \"/(\" + \"/\".join(map(str, nums[1:])) + \")\"\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def optimalDivision(self, nums: List[int]) -> str:\n",
    "        ans=\"\"\n",
    "        if len(nums)==1:\n",
    "            return str(nums[0])\n",
    "        if len(nums)==2:\n",
    "            return str(nums[0])+\"/\"+str(nums[1])\n",
    "        for i in range (len(nums)):\n",
    "            if i ==0:\n",
    "                ans+=str(nums[i])+\"/(\"\n",
    "            elif i==len(nums)-1:\n",
    "                ans+=str(nums[i])+\")\"\n",
    "            else:\n",
    "                ans+=str(nums[i])+\"/\"\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def optimalDivision(self, nums: List[int]) -> str:\n",
    "        n=len(nums)\n",
    "        if n==1:\n",
    "            return str(nums[0])\n",
    "        elif n==2:\n",
    "            return str(nums[0])+'/'+str(nums[1])\n",
    "        else:\n",
    "            res=str(nums[0])+'/('+str(nums[1])\n",
    "            for i in range(2,n):\n",
    "                res+='/'+str(nums[i])\n",
    "            res+=')'\n",
    "            return res\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def optimalDivision(self, nums: List[int]) -> str:\n",
    "        if len(nums)==1:\n",
    "            return str(nums[0])\n",
    "        elif len(nums)==2:\n",
    "            return str(nums[0])+\"/\"+str(nums[1])\n",
    "        else:\n",
    "            s=str(nums[0])+\"/\"+\"(\"\n",
    "            for i in range(1,len(nums)):\n",
    "                s=s+str(nums[i])+\"/\"\n",
    "            s=s[:-1]\n",
    "            s+=\")\"\n",
    "            return s\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def optimalDivision(self, nums: List[int]) -> str:\n",
    "        # 方法1、数学（笑死人不偿命，感觉自己的智商被侮辱了！）\n",
    "        if len(nums) == 1:\n",
    "            return str(nums[0])\n",
    "        if len(nums) == 2:\n",
    "            return str(nums[0]) + \"/\" + str(nums[1])\n",
    "        return str(nums[0]) + \"/\" + \"(\" + \"/\".join(map(str,nums[1:])) + \")\"\n",
    "\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def optimalDivision(self, nums: List[int]) -> str:\n",
    "        # @cache\n",
    "        # def dfs(left, right, exp):\n",
    "        #     if left == right:\n",
    "        #         return nums[left]\n",
    "        #     res = inf\n",
    "        #     for i in range(left, right):\n",
    "        #         res = min(res, dfs(left, i,\"\") / dfs(i + 1, right,\"\"))\n",
    "        #     return res\n",
    "        #\n",
    "        # return nums[0] / dfs(1, len(nums) - 1, f\"{nums[0]}/\")\n",
    "        if len(nums) == 1:\n",
    "            return str(nums[0])\n",
    "        if len(nums) == 2:\n",
    "            return f\"{nums[0]}/{nums[1]}\"\n",
    "        return f\"{nums[0]}/({'/'.join(str(num) for num in nums[1:])})\"\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def optimalDivision(self, nums: List[int]) -> str:\n",
    "        if len(nums) == 1:\n",
    "            return str(nums[0])\n",
    "        if len(nums) == 2:\n",
    "            return str(nums[0]) + \"/\" + str(nums[1])\n",
    "        return str(nums[0]) + \"/(\" + \"/\".join(map(str, nums[1:])) + \")\"\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def optimalDivision(self, nums: List[int]) -> str:\n",
    "        res = \"/\".join(map(str, nums))\n",
    "        if len(nums) > 2:\n",
    "            idx = res.find('/')\n",
    "            return res[:idx + 1] + '(' + res[idx + 1:] + ')'\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def optimalDivision(self, nums: List[int]) -> str:\n",
    "        \n",
    "        \n",
    "        \n",
    "        # my solution ... \n",
    "        \n",
    "        if len(nums) <= 2:\n",
    "            return '/'.join([str(num) for num in nums])\n",
    "        nums = [str(num) for num in nums]\n",
    "        nums[1] = '(' + nums[1]\n",
    "        nums[-1] += ')'\n",
    "        return '/'.join(nums)\n",
    "        \n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def optimalDivision(self, nums: List[int]) -> str:\n",
    "        if len(nums) == 1:\n",
    "            return str(nums[0])\n",
    "        elif len(nums) == 2:\n",
    "            return str(nums[0]) + '/' + str(nums[1])\n",
    "        else:\n",
    "            return str(nums[0]) + '/(' + '/'.join(map(str, nums[1:]))  + ')'"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def optimalDivision(self, nums: List[int]) -> str:\n",
    "        if len(nums) == 1:\n",
    "            return str(nums[0])\n",
    "        if len(nums) == 2:\n",
    "            return str(nums[0]) + \"/\" + str(nums[1])\n",
    "        return str(nums[0]) + \"/(\" + \"/\".join(map(str, nums[1:])) + \")\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def optimalDivision(self, nums: List[int]) -> str:\n",
    "        if len(nums)==1:\n",
    "            return str(nums[0])\n",
    "        if len(nums)==2:\n",
    "            return str(nums[0])+\"/\"+str(nums[1])\n",
    "        return str(nums[0])+\"/(\"+\"/\".join(map(str,nums[1:]))+\")\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def optimalDivision(self, nums: List[int]) -> str:\n",
    "        length = len(nums)\n",
    "        if length == 1:\n",
    "            return str(nums[0])\n",
    "        if length == 2:\n",
    "            return str(nums[0]) + '/' + str(nums[1])\n",
    "        res = '('\n",
    "        for i in range(1, length - 1 ):\n",
    "            res = res + str(nums[i]) + '/'\n",
    "        res = str(nums[0]) + '/' + res + str(nums[length - 1]) + ')'\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def optimalDivision(self, nums: List[int]) -> str:\n",
    "        if len(nums) == 1:\n",
    "            return str(nums[0])\n",
    "        if len(nums) == 2:\n",
    "            return str(nums[0]) + \"/\" + str(nums[1])\n",
    "        return str(nums[0]) + \"/(\" + \"/\".join(map(str, nums[1:])) + \")\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def optimalDivision(self, nums: List[int]) -> str:\n",
    "        if len(nums) == 1:\n",
    "            return str(nums[0])\n",
    "        elif len(nums) == 2:\n",
    "            return str(nums[0]) + '/' + str(nums[1])\n",
    "        return str(nums[0]) + '/(' + '/'.join(map(str, nums[1:])) + ')'"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def optimalDivision(self, nums: List[int]) -> str:\n",
    "        n = len(nums)\n",
    "        if n == 1:\n",
    "            return str(nums[0])\n",
    "        if n == 2:\n",
    "            return str(nums[0]) + \"/\" + str(nums[1])\n",
    "        return str(nums[0]) + \"/(\" + \"/\".join(map(str, nums[1:])) + \")\"\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def optimalDivision(self, nums: List[int]) -> str:\n",
    "        if len(nums) == 1:\n",
    "            return str(nums[0])\n",
    "        if len(nums) == 2:\n",
    "            return str(nums[0]) + \"/\" + str(nums[1])\n",
    "        return str(nums[0]) + \"/(\" + \"/\".join(map(str, nums[1:])) + \")\"\n",
    "\n",
    "# 作者：力扣官方题解\n",
    "# 链接：https://leetcode.cn/problems/optimal-division/solutions/1283208/zui-you-chu-fa-by-leetcode-solution-lf4c/\n",
    "# 来源：力扣（LeetCode）\n",
    "# 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def optimalDivision(self, nums: List[int]) -> str:\n",
    "        if len(nums) == 1:\n",
    "            return str(nums[0])\n",
    "        elif len(nums) == 2:\n",
    "            return str(\"{}/{}\".format(nums[0], nums[1]))\n",
    "        result = \"\"\n",
    "        for (idx, num) in enumerate(nums):\n",
    "            if idx == 1:\n",
    "                result += \"({}/\".format(nums[idx])\n",
    "            elif idx == len(nums) - 1:\n",
    "                result += \"{})\".format(nums[idx])\n",
    "            else:\n",
    "                result += \"{}/\".format(nums[idx])\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def optimalDivision(self, nums: List[int]) -> str:\n",
    "        if len(nums)==1:\n",
    "            return str(nums[0])\n",
    "        elif len(nums)==2:\n",
    "            return f'{nums[0]}/{nums[1]}'\n",
    "        else:\n",
    "            ans=f'{nums[0]}/({nums[1]}'\n",
    "            for i in range(2,len(nums)):\n",
    "                ans+='/'+str(nums[i])\n",
    "            return ans+')'"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def optimalDivision(self, nums: List[int]) -> str:\n",
    "        if len(nums) == 1:\n",
    "            return str(nums[0])\n",
    "        if len(nums) == 2:\n",
    "            return str(nums[0]) + \"/\" + str(nums[1])\n",
    "        return str(nums[0]) + \"/(\" + \"/\".join(map(str, nums[1:])) + \")\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def optimalDivision(self, nums: List[int]) -> str:\n",
    "        if len(nums)==1:\n",
    "            result=str(nums[0])\n",
    "        elif len(nums)==2:\n",
    "            result=str(nums[0])+'/'+str(nums[1])\n",
    "        else:\n",
    "            result=str(nums[0])+'/('+'/'.join(map(lambda a:str(a),nums[1:len(nums)]))+')'\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def optimalDivision(self, nums: List[int]) -> str:\n",
    "        if len(nums) == 1:\n",
    "            return str(nums[0])\n",
    "        if len(nums) == 2:\n",
    "            return f\"{nums[0]}/{nums[1]}\"\n",
    "        ans = []\n",
    "        for i, n in enumerate(nums):\n",
    "            s = str(n)\n",
    "            if i == 1:\n",
    "                s = '(' + s\n",
    "            if i == len(nums) - 1:\n",
    "                s += ')'\n",
    "            ans.append(s)\n",
    "        return '/'.join(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Node:\n",
    "    def __init__(self):\n",
    "        self.minVal = 1e4\n",
    "        self.maxVal = 0\n",
    "        self.minStr = \"\"\n",
    "        self.maxStr = \"\"\n",
    "\n",
    "class Solution:\n",
    "    def optimalDivision(self, nums: List[int]) -> str:\n",
    "        n = len(nums)\n",
    "        dp = [[Node() for _ in range(n)] for _ in range(n)]\n",
    "        for i, num in enumerate(nums):\n",
    "            dp[i][i].minVal = num\n",
    "            dp[i][i].maxVal = num\n",
    "            dp[i][i].minStr = str(num)\n",
    "            dp[i][i].maxStr = str(num)\n",
    "        for i in range(n):\n",
    "            for j in range(n - i):\n",
    "                for k in range(j, j + i):\n",
    "                    if dp[j][j + i].maxVal < dp[j][k].maxVal / dp[k + 1][j + i].minVal:\n",
    "                        dp[j][j + i].maxVal = dp[j][k].maxVal / dp[k + 1][j + i].minVal\n",
    "                        if k + 1 == j + i:\n",
    "                            dp[j][j + i].maxStr = dp[j][k].maxStr + \"/\" + dp[k + 1][j + i].minStr\n",
    "                        else:\n",
    "                            dp[j][j + i].maxStr = dp[j][k].maxStr + \"/(\" + dp[k + 1][j + i].minStr + \")\"\n",
    "                    if dp[j][j + i].minVal > dp[j][k].minVal / dp[k + 1][j + i].maxVal:\n",
    "                        dp[j][j + i].minVal = dp[j][k].minVal / dp[k + 1][j + i].maxVal\n",
    "                        if k + 1 == j + i:\n",
    "                            dp[j][j + i].minStr = dp[j][k].minStr + \"/\" + dp[k + 1][j + i].maxStr\n",
    "                        else:\n",
    "                            dp[j][j + i].minStr = dp[j][k].minStr + \"/(\" + dp[k + 1][j + i].maxStr + \")\"\n",
    "        return dp[0][n - 1].maxStr"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def optimalDivision(self, nums: List[int]) -> str:\n",
    "        n = len(nums)\n",
    "        b = []\n",
    "        for i in range(n - 1):\n",
    "            b.append(str(nums[i]))\n",
    "            b.append('/')\n",
    "        if n > 2:\n",
    "            b.append(str(nums[-1]))\n",
    "            b.append(')')\n",
    "            b.insert(b.index('/') + 1,'(')\n",
    "        else:\n",
    "            b.append(str(nums[-1]))\n",
    "        # print(b)\n",
    "        res = ''.join(b)\n",
    "        return res\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def optimalDivision(self, nums: List[int]) -> str:\n",
    "        return \"/\".join(map(str,nums)) if len(nums) <= 2 else \"{}/({})\".format(nums[0],\"/\".join(map(str,nums[1:])))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def optimalDivision(self, nums: List[int]) -> str:\n",
    "        if len(nums) == 1:\n",
    "            return str(nums[0])\n",
    "        if len(nums) == 2:\n",
    "            return f\"{nums[0]}/{nums[1]}\"\n",
    "        res = f\"{nums[0]}/({nums[1]}\"\n",
    "        for i in nums[2:]:\n",
    "            res += f\"/{i}\"\n",
    "\n",
    "        return res + \")\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def optimalDivision(self, nums: List[int]) -> str:\n",
    "        if len(nums) == 1:\n",
    "            return str(nums[0])\n",
    "        if len(nums) == 2:\n",
    "            return str(nums[0]) + \"/\" + str(nums[1])\n",
    "        return str(nums[0]) + \"/(\" + \"/\".join(map(str, nums[1:])) + \")\"\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Node:\n",
    "    def __init__(self):\n",
    "        self.minVal = 1e4\n",
    "        self.maxVal = 0\n",
    "        self.minStr = \"\"\n",
    "        self.maxStr = \"\"\n",
    "\n",
    "class Solution:\n",
    "    def optimalDivision(self, nums: List[int]) -> str:\n",
    "        n = len(nums)\n",
    "        dp = [[Node() for _ in range(n)] for _ in range(n)]\n",
    "        for i, num in enumerate(nums):\n",
    "            dp[i][i].minVal = num\n",
    "            dp[i][i].maxVal = num\n",
    "            dp[i][i].minStr = str(num)\n",
    "            dp[i][i].maxStr = str(num)\n",
    "        for i in range(n):\n",
    "            for j in range(n - i):\n",
    "                for k in range(j, j + i):\n",
    "                    if dp[j][j + i].maxVal < dp[j][k].maxVal / dp[k + 1][j + i].minVal:\n",
    "                        dp[j][j + i].maxVal = dp[j][k].maxVal / dp[k + 1][j + i].minVal\n",
    "                        if k + 1 == j + i:\n",
    "                            dp[j][j + i].maxStr = dp[j][k].maxStr + \"/\" + dp[k + 1][j + i].minStr\n",
    "                        else:\n",
    "                            dp[j][j + i].maxStr = dp[j][k].maxStr + \"/(\" + dp[k + 1][j + i].minStr + \")\"\n",
    "                    if dp[j][j + i].minVal > dp[j][k].minVal / dp[k + 1][j + i].maxVal:\n",
    "                        dp[j][j + i].minVal = dp[j][k].minVal / dp[k + 1][j + i].maxVal\n",
    "                        if k + 1 == j + i:\n",
    "                            dp[j][j + i].minStr = dp[j][k].minStr + \"/\" + dp[k + 1][j + i].maxStr\n",
    "                        else:\n",
    "                            dp[j][j + i].minStr = dp[j][k].minStr + \"/(\" + dp[k + 1][j + i].maxStr + \")\"\n",
    "        return dp[0][n - 1].maxStr\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def optimalDivision(self, nums: List[int]) -> str:\n",
    "        l = list(map(str, nums))\n",
    "        if len(l) > 2:\n",
    "            l[1] = '(' + l[1]\n",
    "            l[-1] = l[-1] + ')'\n",
    "        return '/'.join(l)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def optimalDivision(self, nums: List[int]) -> str:\n",
    "        if(len(nums) <= 2):\n",
    "            return '/'.join([str(num) for num in nums])\n",
    "        total_mul = 1\n",
    "        for num in nums:\n",
    "            total_mul = total_mul*num\n",
    "        score = 0\n",
    "        mul = nums[0]\n",
    "        division = nums[0]\n",
    "        idx = 0\n",
    "        for i in range(1,len(nums)):\n",
    "            division = division/nums[i]\n",
    "            mul = mul*nums[i]\n",
    "            tmul = total_mul//mul\n",
    "            if(division*tmul > score):\n",
    "                score = division*tmul\n",
    "                idx = i \n",
    "        strs = [str(num) for num in nums]\n",
    "        return '/'.join(strs[:idx]) + '/(' + '/'.join(strs[idx:]) + ')'\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# class Solution:\r\n",
    "#     def optimalDivision(self, nums: List[int]) -> str:\r\n",
    "#         s = ''\r\n",
    "#         n = len(nums)\r\n",
    "#         if n == 1:\r\n",
    "#             return str(nums[0])\r\n",
    "#         for i in range(n - 1):\r\n",
    "#             if i == 1:\r\n",
    "#                 s += '('\r\n",
    "#             s  += str(nums[i]) + '/'\r\n",
    "#         s += str(nums[-1])\r\n",
    "#         if n > 2:\r\n",
    "#             s += ')'\r\n",
    "#         return s\r\n",
    "\r\n",
    "class Solution:\r\n",
    "    def optimalDivision(self, nums: List[int]) -> str:\r\n",
    "        if len(nums) == 1:\r\n",
    "            return str(nums[0])\r\n",
    "        if len(nums) == 2:\r\n",
    "            return str(nums[0]) + \"/\" + str(nums[1])\r\n",
    "        return str(nums[0]) + \"/(\" + \"/\".join(map(str, nums[1:])) + \")\"\r\n",
    "\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def optimalDivision(self, nums: List[int]) -> str:\n",
    "        if len(nums) == 1: return str(nums[0])\n",
    "        if len(nums) == 2: return str(nums[0]) + '/' + str(nums[1])\n",
    "        ans = str(nums[0]) + '/('\n",
    "        for i in range(1, len(nums)):\n",
    "            if i > 1: ans += '/'\n",
    "            ans += str(nums[i])\n",
    "        ans += ')'\n",
    "        return ans\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def optimalDivision(self, nums: List[int]) -> str:\n",
    "        n = len(nums)\n",
    "        if n==1:\n",
    "            return str(nums[0])\n",
    "        if n==2:\n",
    "            return str(nums[0]) + \"/\" + str(nums[1])\n",
    "        return str(nums[0]) +\"/(\"+\"/\".join(map(str,nums[1:]))+\")\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def optimalDivision(self, nums: List[int]) -> str:\r\n",
    "        nums=[str(n) for n in nums]\r\n",
    "        if len(nums)<3:\r\n",
    "            return '/'.join(nums)\r\n",
    "        return f'{nums[0]}/({\"/\".join(nums[1:])})'"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def optimalDivision(self, nums: List[int]) -> str:\n",
    "        return \"/\".join(map(str, nums)) if len(nums) <= 2 else \"{}/({})\".format(nums[0], \"/\".join(map(str, nums[1:])))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def optimalDivision(self, nums: List[int]) -> str:\n",
    "        if len(nums) == 1:\n",
    "            return str(nums[0])\n",
    "        if len(nums) ==2:\n",
    "            return '{}/{}'.format(nums[0],nums[1])\n",
    "        return '{}/({})'.format(nums[0],'/'.join(str(num) for num in nums[1:]))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def optimalDivision(self, nums: List[int]) -> str:\n",
    "        n = len(nums)\n",
    "        if n <= 2:\n",
    "            return '/'.join([str(i) for i in nums])\n",
    "        else:\n",
    "            return str(nums[0])+\"/(\"+'/'.join([str(i) for i in nums[1:]])+\")\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def optimalDivision(self, nums: List[int]) -> str:\n",
    "        if len(nums)==1:\n",
    "            return str(nums[0])\n",
    "        elif len(nums)==2:\n",
    "            return '/'.join(map(str,nums))\n",
    "        nums[1]='('+str(nums[1])\n",
    "        nums[-1]=str(nums[-1])+')'\n",
    "        return '/'.join(map(str,nums))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def optimalDivision(self, nums: List[int]) -> str:\n",
    "        nums = list(map(str, nums))\n",
    "        if len(nums) == 1:\n",
    "            return nums[0]\n",
    "        elif len(nums) == 2:\n",
    "            return f\"{nums[0]}/{nums[1]}\"\n",
    "        k = \"/\".join(nums[1:])\n",
    "        return f\"{nums[0]}/({k})\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def optimalDivision(self, nums: List[int]) -> str:\n",
    "        # 产生最小的结果，即不加任何括号；因为只要加入括号就会使得分母变小，导致结果变大\n",
    "        # 产生最大的结果，即让除了第一项之外的数组乘积最小，得到最小分母，那就是只加一次括号\n",
    "        if len(nums) == 1:\n",
    "            return str(nums[0])\n",
    "        elif len(nums) == 2:\n",
    "            return str(nums[0]) + '/' + str(nums[1]) \n",
    "        res = str(nums[0]) + '/('\n",
    "        for i in range(1, len(nums)):\n",
    "            res += str(nums[i]) + '/'\n",
    "        res = res[:-1] + ')'\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def optimalDivision(self, nums: List[int]) -> str:\n",
    "        if len(nums) == 1:\n",
    "            return str(nums[0])\n",
    "        if len(nums) == 2:\n",
    "            return str(nums[0]) + \"/\" + str(nums[1])\n",
    "        return str(nums[0]) + \"/(\" + \"/\".join(map(str, nums[1:])) + \")\"\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def optimalDivision(self, nums: List[int]) -> str:\n",
    "        # 下层返回最小结果 暴露给上层\n",
    "        def dfs(left, right, flag = False):\n",
    "            if left == right - 1:\n",
    "                return f'{nums[left]}/{nums[right]}'\n",
    "            print(left, right)\n",
    "            res_string = '/'.join([str(x) for x in nums[left:right+1]])\n",
    "            cur_res = eval(res_string)\n",
    "            print(res_string, cur_res)\n",
    "            for i in range(left + 1, right):\n",
    "                for j in range(i + 1, right + 1):\n",
    "                    string = dfs(i, j)\n",
    "                    numbers = [str(x) for x in nums[left:i]] + [f'({string})'] + [str(x) for x in nums[j + 1:right + 1]]\n",
    "                    target_str = '/'.join(numbers)\n",
    "                    # print(i, j, target_str)\n",
    "                    calc = eval(target_str)\n",
    "                    if flag and calc > cur_res:\n",
    "                        res_string = target_str\n",
    "                        cur_res = calc\n",
    "                    elif not flag and calc < cur_res:\n",
    "                        res_string = target_str\n",
    "                        cur_res = calc\n",
    "            return res_string\n",
    "        \n",
    "        return dfs(0, len(nums) - 1, True)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def optimalDivision(self, nums: List[int]) -> str:\n",
    "        if(len(nums) <= 2):\n",
    "            return '/'.join([str(num) for num in nums])\n",
    "        total_mul = 1\n",
    "        for num in nums:\n",
    "            total_mul = total_mul*num\n",
    "        score = 0\n",
    "        mul = nums[0]\n",
    "        division = nums[0]\n",
    "        idx = 0\n",
    "        for i in range(1,len(nums)):\n",
    "            division = division/nums[i]\n",
    "            mul = mul*nums[i]\n",
    "            tmul = total_mul//mul\n",
    "            if(division*tmul > score):\n",
    "                score = division*tmul\n",
    "                idx = i \n",
    "        strs = [str(num) for num in nums]\n",
    "        return '/'.join(strs[:idx]) + '/(' + '/'.join(strs[idx:]) + ')'\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def optimalDivision(self, nums: List[int]) -> str:\n",
    "        e = ''\n",
    "\n",
    "        if len(nums)==1:\n",
    "            return str(nums[0])\n",
    "        if len(nums)==2:\n",
    "            return f'{nums[0]}/{nums[1]}'\n",
    "\n",
    "        nums = [str(i) for i in nums]\n",
    "\n",
    "        for i in range(len(nums)):\n",
    "            if i==0:\n",
    "                e += (nums[i]+'/(')\n",
    "            else:\n",
    "                e += nums[i]\n",
    "                if i!=len(nums)-1:\n",
    "                    e += '/'\n",
    "\n",
    "        e += ')'\n",
    "\n",
    "        return e"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def optimalDivision(self, nums: List[int]) -> str:\n",
    "        n=len(nums)\n",
    "        if n==1:\n",
    "            return str(nums[0])\n",
    "        if n==2:\n",
    "            return str(nums[0])+'/'+str(nums[1])\n",
    "        return str(nums[0])+'/('+'/'.join(map(str,nums[1:]))+')'"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def optimalDivision(self, nums: List[int]) -> str:\r\n",
    "        s = ''\r\n",
    "        n = len(nums)\r\n",
    "        if n == 1:\r\n",
    "            return str(nums[0])\r\n",
    "        for i in range(n - 1):\r\n",
    "            if i == 1:\r\n",
    "                s += '('\r\n",
    "            s  += str(nums[i]) + '/'\r\n",
    "        s += str(nums[-1])\r\n",
    "        if n > 2:\r\n",
    "            s += ')'\r\n",
    "        return s\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def optimalDivision(self, nums: List[int]) -> str:\n",
    "        if len(nums) == 1:\n",
    "            return str(nums[0])\n",
    "        if len(nums) == 2:\n",
    "            return str(nums[0]) + \"/\" + str(nums[1])\n",
    "        return str(nums[0]) + \"/(\" + \"/\".join(map(str, nums[1:])) + \")\"\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def optimalDivision(self, nums: List[int]) -> str:  \n",
    "        if len(nums)==1:\n",
    "            return str(nums[0])\n",
    "        if len(nums)==2:\n",
    "            return str(nums[0])+\"/\"+str(nums[1])\n",
    "        return str(nums[0])+\"/(\"+\"/\".join(map(str,nums[1:]))+\")\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def optimalDivision(self, nums: List[int]) -> str:\n",
    "        if len(nums) == 1:\n",
    "            return str(nums[0])\n",
    "        if len(nums) == 2:\n",
    "            return str(nums[0]) + \"/\" + str(nums[1])\n",
    "        return str(nums[0]) + \"/(\" + \"/\".join(map(str, nums[1:])) + \")\"\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def optimalDivision(self, nums: List[int]) -> str:\n",
    "        return \"/\".join(map(str, nums)) if len(nums) <= 2 else \"{}/({})\".format(nums[0], \"/\".join(map(str, nums[1:])))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def optimalDivision(self, nums: List[int]) -> str:\n",
    "        if len(nums) == 1:\n",
    "            return str(nums[0])\n",
    "        if len(nums) == 2:\n",
    "            return str(nums[0])+'/'+str(nums[1])\n",
    "        res = ''\n",
    "        for i in range(len(nums)):\n",
    "            if i == 0:\n",
    "                res += str(nums[i])\n",
    "                res += '/('\n",
    "            elif i == len(nums)-1:\n",
    "                res += str(nums[i])\n",
    "                res += ')'\n",
    "            else:\n",
    "                res += str(nums[i])\n",
    "                res += '/'\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def optimalDivision(self, nums: List[int]) -> str:\n",
    "        ret=''\n",
    "        i=0\n",
    "        while i<len(nums):\n",
    "            if i==1 and len(nums)>2:\n",
    "                ret+='('+str(nums[i])+'/'+str(nums[i+1])+'/'\n",
    "                i+=2\n",
    "                continue\n",
    "            ret+=str(nums[i])+'/'\n",
    "            i+=1\n",
    "        if len(nums)>2:\n",
    "            ret=ret[:-1]+')'\n",
    "        else:\n",
    "            ret=ret[:-1]\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def optimalDivision(self, nums: List[int]) -> str:\n",
    "        if len(nums)==1:\n",
    "            return str(nums[0])\n",
    "        elif len(nums)==2:\n",
    "            return str(nums[0])+\"/\"+str(nums[1])\n",
    "        l=list(map(str,nums))\n",
    "        l[1]=\"(\"+l[1]\n",
    "        l[-1]+=\")\"\n",
    "        ans=\"/\".join(l)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Node:\n",
    "    def __init__(self):\n",
    "        self.minVal = 1e4\n",
    "        self.maxVal = 0\n",
    "        self.minStr = \"\"\n",
    "        self.maxStr = \"\"\n",
    "\n",
    "class Solution:\n",
    "    def optimalDivision(self, nums: List[int]) -> str:\n",
    "        n = len(nums)\n",
    "        dp = [[Node() for _ in range(n)] for _ in range(n)]\n",
    "        for i, num in enumerate(nums):\n",
    "            dp[i][i].minVal = num\n",
    "            dp[i][i].maxVal = num\n",
    "            dp[i][i].minStr = str(num)\n",
    "            dp[i][i].maxStr = str(num)\n",
    "        for i in range(n):\n",
    "            for j in range(n - i):\n",
    "                for k in range(j, j + i):\n",
    "                    if dp[j][j + i].maxVal < dp[j][k].maxVal / dp[k + 1][j + i].minVal:\n",
    "                        dp[j][j + i].maxVal = dp[j][k].maxVal / dp[k + 1][j + i].minVal\n",
    "                        if k + 1 == j + i:\n",
    "                            dp[j][j + i].maxStr = dp[j][k].maxStr + \"/\" + dp[k + 1][j + i].minStr\n",
    "                        else:\n",
    "                            dp[j][j + i].maxStr = dp[j][k].maxStr + \"/(\" + dp[k + 1][j + i].minStr + \")\"\n",
    "                    if dp[j][j + i].minVal > dp[j][k].minVal / dp[k + 1][j + i].maxVal:\n",
    "                        dp[j][j + i].minVal = dp[j][k].minVal / dp[k + 1][j + i].maxVal\n",
    "                        if k + 1 == j + i:\n",
    "                            dp[j][j + i].minStr = dp[j][k].minStr + \"/\" + dp[k + 1][j + i].maxStr\n",
    "                        else:\n",
    "                            dp[j][j + i].minStr = dp[j][k].minStr + \"/(\" + dp[k + 1][j + i].maxStr + \")\"\n",
    "        return dp[0][n - 1].maxStr"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def optimalDivision(self, nums: List[int]) -> str:\n",
    "      if len(nums) == 1:  return str(nums[0])\n",
    "      if len(nums) == 2:  return str(nums[0]) + \"/\" + str(nums[1])\n",
    "      ans = [str(nums[0]), \"/(\"]\n",
    "      for num in nums[1:]:\n",
    "        ans.append(str(num))\n",
    "        ans.append(\"/\")\n",
    "      ans[-1] = \")\"\n",
    "      return \"\".join(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def optimalDivision(self, nums: List[int]) -> str:\n",
    "        # 下层返回最小结果 暴露给上层\n",
    "        dp = {}\n",
    "        def dfs(left, right, flag = False):\n",
    "            if left == right - 1:\n",
    "                return f'{nums[left]}/{nums[right]}'\n",
    "            if not dp.get((left, right), None) == None:\n",
    "                return dp.get((left, right))\n",
    "            res_string = '/'.join([str(x) for x in nums[left:right+1]])\n",
    "            cur_res = eval(res_string)\n",
    "            for i in range(left + 1, right):\n",
    "                for j in range(i + 1, right + 1):\n",
    "                    string = dfs(i, j)\n",
    "                    numbers = [str(x) for x in nums[left:i]] + [f'({string})'] + [str(x) for x in nums[j + 1:right + 1]]\n",
    "                    target_str = '/'.join(numbers)\n",
    "                    # print(i, j, target_str)\n",
    "                    calc = eval(target_str)\n",
    "                    if flag and calc > cur_res:\n",
    "                        res_string = target_str\n",
    "                        cur_res = calc\n",
    "                    elif not flag and calc < cur_res:\n",
    "                        res_string = target_str\n",
    "                        cur_res = calc\n",
    "            dp[(left, right)] = res_string\n",
    "            return res_string\n",
    "        \n",
    "        return dfs(0, len(nums) - 1, True)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def optimalDivision(self, nums: List[int]) -> str:\n",
    "      [a, *other] = nums\n",
    "      if len(other) == 0: return str(a)\n",
    "      if len(other) == 1: return f\"{a}/{other[0]}\"\n",
    "      return str(a) + \"/(\" + '/'.join([str(i) for i in other]) + ')'"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def optimalDivision(self, nums: List[int]) -> str:\n",
    "        n = len(nums)\n",
    "        nums = [str(x) for x in nums]\n",
    "        if n == 1:\n",
    "            return nums[0]\n",
    "        if n <= 2:\n",
    "            return '/'.join(nums)\n",
    "        return '{}/({})'.format(nums[0], '/'.join(nums[1:]))\n",
    "        # @lru_cache(None)\n",
    "        # def dfs(st, en):\n",
    "        #     if st == en:\n",
    "        #         return nums[st], nums[st]\n",
    "        #     mn, mx = float('inf'), 0\n",
    "        #     for mid in range(st, en):\n",
    "        #         lmn, lmx = dfs(st, mid)\n",
    "        #         rmn, rmx = dfs(mid+1, en)\n",
    "        #         mn = min(mn, lmn / rmx)\n",
    "        #         mx = max(mx, lmx / rmn)\n",
    "        #     return mn, mx\n",
    "\n",
    "        # return dfs(0, n-1)[1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def optimalDivision(self, nums: List[int]) -> str:\r\n",
    "        first = nums[0]\r\n",
    "        if len(nums) == 1:\r\n",
    "            return str(first)\r\n",
    "        if len(nums) == 2:\r\n",
    "            return str(first) + '/' + str(nums[1])\r\n",
    "        return str(first) + '/(' + '/'.join(map(str, nums[1:])) + ')'"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Node:\n",
    "    def __init__(self):\n",
    "        self.minVal = 1e4\n",
    "        self.maxVal = 0\n",
    "        self.minStr = \"\"\n",
    "        self.maxStr = \"\"\n",
    "\n",
    "class Solution:\n",
    "    def optimalDivision(self, nums: List[int]) -> str:\n",
    "        n = len(nums)\n",
    "        dp = [[Node() for _ in range(n)] for _ in range(n)]\n",
    "        for i, num in enumerate(nums):\n",
    "            dp[i][i].minVal = num\n",
    "            dp[i][i].maxVal = num\n",
    "            dp[i][i].minStr = str(num)\n",
    "            dp[i][i].maxStr = str(num)\n",
    "        for i in range(n):\n",
    "            for j in range(n - i):\n",
    "                for k in range(j, j + i):\n",
    "                    if dp[j][j + i].maxVal < dp[j][k].maxVal / dp[k + 1][j + i].minVal:\n",
    "                        dp[j][j + i].maxVal = dp[j][k].maxVal / dp[k + 1][j + i].minVal\n",
    "                        if k + 1 == j + i:\n",
    "                            dp[j][j + i].maxStr = dp[j][k].maxStr + \"/\" + dp[k + 1][j + i].minStr\n",
    "                        else:\n",
    "                            dp[j][j + i].maxStr = dp[j][k].maxStr + \"/(\" + dp[k + 1][j + i].minStr + \")\"\n",
    "                    if dp[j][j + i].minVal > dp[j][k].minVal / dp[k + 1][j + i].maxVal:\n",
    "                        dp[j][j + i].minVal = dp[j][k].minVal / dp[k + 1][j + i].maxVal\n",
    "                        if k + 1 == j + i:\n",
    "                            dp[j][j + i].minStr = dp[j][k].minStr + \"/\" + dp[k + 1][j + i].maxStr\n",
    "                        else:\n",
    "                            dp[j][j + i].minStr = dp[j][k].minStr + \"/(\" + dp[k + 1][j + i].maxStr + \")\"\n",
    "        return dp[0][n - 1].maxStr\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
